package 链表.单向.练习;
//合并有序列表
public class Text_4 {
    public ListNode head;
    public void addFirst(int data){
        //代码不能交换
        //必须先绑定信息
        ListNode listNode = new ListNode(data);
        listNode.next = head;
        head = listNode;
    }
    void display(){
        ListNode cur = head;
        while (cur!=null){
            System.out.print(cur.val+" ");
            cur = cur.next;//cur向后走一步
        }
        System.out.println();
    }
    static ListNode mergeTwoLists(ListNode headA,ListNode headB){
        ListNode newHead = new ListNode();
        ListNode tmphead = newHead;//必须使用虚拟节点，否则无法正确返回合并后的链表
        while(headA!= null&&headB!=null){
            if(headA.val>= headB.val){
                tmphead.next = headB;
                headB =headB.next;
                tmphead = tmphead.next;
            }else{
                tmphead.next = headA;
                headA = headA.next;
                tmphead = tmphead.next;
            }
        }
        if(headA!=null){
            tmphead.next = headA;
        }
        if(headB!=null){
            tmphead.next = headB;
        }
        return newHead.next;
    }

    public static void main(String[] args) {
        Text_4 text4 = new Text_4();
        text4.addFirst(6);
        text4.addFirst(2);
        text4.addFirst(1);
        ListNode headA = text4.head;
        text4.display();

        Text_4 text41 = new Text_4();
        text41.addFirst(9);
        text41.addFirst(5);
        text41.addFirst(3);
        ListNode headB = text41.head;
        text41.display();

        ListNode newHead ;
        newHead = mergeTwoLists(headA,headB);
        ListNode cur = newHead;
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur = cur.next;
        }

    }
}
